\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}

\title{作业二: \textbf{BST排序算法}的实现}


\author{胡宇梦 \\ 信息与计算科学　3210103435}


\begin{document}

\maketitle




\section{二叉树定义}
二叉排序树或者是一棵空树，或者是一棵有下列性质的二叉树:

\begin{enumerate}
\item 若它的左子树不为空，则它左子树上所有结点的值必然小于根结点的值。
\item 若它的右子树不为空，则它右子树上所有结点的值必然大于根结点的值
\item 它的左右子树也为二叉排序树。

\end{enumerate}




\section{二叉树的设计}
\begin{enumerate}
  \item \textbf{定义二叉树的节点类}


\begin{verbatim}
struct BinaryNode
    {
        Comparable element;
        BinaryNode* left;
        BinaryNode* right;

        BinaryNode(const Comparable& theElement, BinaryNode* lt, BinaryNode* rt)
            : element{ theElement }, left{ lt }, right{ rt } { }

        BinaryNode(Comparable&& theElement, BinaryNode* lt, BinaryNode* rt)
            : element{ std::move(theElement) }, left{ lt }, right{ rt } { }
    };

    BinaryNode* root;
\end{verbatim}
\end{enumerate}


\section{方法的实现}
\begin{enumerate}

\item \textbf{创建二叉搜索树对象 t}  


代码如下： 
\begin{verbatim}
BinarySearchTree<int> t;
\end{verbatim}

\item \textbf{插入数据 insert()}


代码如下： 
\begin{verbatim}
void insert(const Comparable& x, BinaryNode*& t)
    {
        if (t == nullptr)
            t = new BinaryNode{ x, nullptr, nullptr };
        else if (x < t->element)
            insert(x, t->left);
        else if (t->element < x)
            insert(x, t->right);
        else
            ;  // Duplicate; do nothing
    }

void insert(Comparable&& x, BinaryNode*& t)
    {
        if (t == nullptr)
            t = new BinaryNode{ std::move(x), nullptr, nullptr };
        else if (x < t->element)
            insert(std::move(x), t->left);
        else if (t->element < x)
            insert(std::move(x), t->right);
        else
            ;  // Duplicate; do nothing
    }
\end{verbatim}


\item \textbf{移除数据remove()}  


代码如下： 
\begin{verbatim}
void remove(const Comparable& x, BinaryNode*& t)
    {
        if (t == nullptr)
            return;   // Item not found; do nothing
        if (x < t->element)
            remove(x, t->left);
        else if (t->element < x)
            remove(x, t->right);
        else if (t->left != nullptr && t->right != nullptr) // Two children
        {
            t->element = findMin(t->right)->element;
            remove(t->element, t->right);
        }
        else
        {
            BinaryNode* oldNode = t;
            t = (t->left != nullptr) ? t->left : t->right;
            delete oldNode;
        }
    }
\end{verbatim}

\item \textbf{寻找最小元素findMin()}  


代码如下： 
\begin{verbatim}
BinaryNode* findMin(BinaryNode* t) const
    {
        if (t == nullptr)
            return nullptr;
        if (t->left == nullptr)
            return t;
        return findMin(t->left);
    }
\end{verbatim}

\item \textbf{寻找最大元素findMax()}  


代码如下： 
\begin{verbatim}
BinaryNode* findMax(BinaryNode* t) const
    {
        if (t != nullptr)
            while (t->right != nullptr)
                t = t->right;
        return t;
    }
\end{verbatim}



\item \textbf{判断是否包含元素contains()}


代码如下： 
\begin{verbatim}
    bool contains(const Comparable& x, BinaryNode* t) const
    {
        if (t == nullptr)
            return false;
        else if (x < t->element)
            return contains(x, t->left);
        else if (t->element < x)
            return contains(x, t->right);
        else
            return true;    // Match
    }
\end{verbatim}


\item \textbf{清空二叉树对象makeEmpty()}


代码如下： 
\begin{verbatim}
void makeEmpty(BinaryNode*& t)
    {
        if (t != nullptr)
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        t = nullptr;
    }
\end{verbatim}


\item \textbf{排序输出printTree()}


代码如下： 
\begin{verbatim}
void printTree(BinaryNode* t, ostream& out) const
    {
        if (t != nullptr)
        {
            printTree(t->left, out);
            out << t->element << endl;
            printTree(t->right, out);
        }
    }
\end{verbatim}

\item \textbf{自定义外部函数 乱序数组RandomVector()}


代码如下： 
\begin{verbatim}
template <typename Comparable>
vector<Comparable> RandomVector(std::vector<Comparable>& _arr)
    {
        std::vector<Comparable> new_arr;        ///生成新数组
        int i;
        for (i = _arr.size(); i > 0; i--)
        {
            srand(unsigned(time(NULL)));
            /// index记录选中的随机下标
            int index = rand() % i;
            /// 将选中下标对应的元素push到新数组
            new_arr.push_back(_arr[index]);
            /// 将原数组中选中的元素剔除
            _arr.erase(_arr.begin() + index);
        }
        
        /// 返回新数组
        return new_arr;
    };
\end{verbatim}

\item \textbf{自定义外部函数 排序数组BSTsorting()}


代码如下： 
\begin{verbatim}
template <typename Comparable>
void BSTSorting(std::vector<Comparable>& _arr,int _mode )
    {
        int j;
        BinarySearchTree<Comparable> m;     ///定义对象m
    
        if (_mode == 0)    
        {
            for (j = 0; j < _arr.size(); j++)
            {
                m.insert(_arr[j]);
            }
            m.printTree();       ///直接输出数组
        }
        else
        {
            _arr = RandomVector(_arr);       ///调用RandomVector将数组乱序
           
            for (j = 0; j < _arr.size(); j++)
            {
                 cout << _arr[j] << endl;            ///输出乱序数组
            } 
            
            for (j = 0; j < _arr.size(); j++)
            {
                 m.insert(_arr[j]);                         
            }
              m.printTree();                                  ///排序后输出
        }
    };
\end{verbatim}

\end{enumerate}


\section{测试说明}

\begin{enumerate}
    \item \textbf{方法的测试}

    测试代码如下：
\begin{verbatim}
    BinarySearchTree<int> t;
    int NUMS = 20;
    const int GAP = 3711;
    int i;

    cout << "Checking... (no more output means success)" << endl;

    /**
     * @brief 在 t 中插入元素
     * 
     */
    for (i = GAP; i != 0; i = (i + GAP) % NUMS)
        t.insert(i);
    
    /**
     * @brief 剔除 t 中的奇数元素
     * 
     */
    for (i = 1; i < NUMS; i += 2)
        t.remove(i);

    /// 排序输出小于40的元素
    if (NUMS < 40)
        t.printTree();
    /// 测试函数findmin()和findmax()
    if (t.findMin() != 2 || t.findMax() != std::max(NUMS - 2,GAP))
        cout << "FindMin or FindMax error!" << endl;
    
    /// 测试函数contains()
    for (i = 2; i < NUMS; i += 2)
        if (!t.contains(i))
            cout << "Find error1!" << endl;

    for (i = 1; i < NUMS; i += 2)
    {
        if (t.contains(i))
            cout << "Find error2!" << endl;
    }

    /// 测试重载运算符 =
    BinarySearchTree<int> t2;
    t2 = t;

    for (i = 2; i < NUMS; i += 2)
        if (!t2.contains(i))
            cout << "Find error1!" << endl;

    for (i = 1; i < NUMS; i += 2)
    {
        if (t2.contains(i))
            cout << "Find error2!" << endl;
    }

    cout << "Finished testing" << endl;

    /**
     * @brief 构造数组obj
     * 
     */
    vector<int>obj;
    for (i = 5; i >0; i--)
    {
        obj.push_back(i);
    }

    BSTSorting(obj, 0); 
    BSTSorting(obj, 1); 

\end{verbatim}

测试结果：
\begin{figure}[htbp]
  \centering
  \includegraphics[scale=0.2]{1.png}
  \caption{方法测试结果}
\end{figure} 
    




    \item \textbf{效率的测试(以 t 只包含 1 到 10 的元素为例)}
    
    
    2.1     \textbf{$\_mode = 0$时的最坏效率} 
    
    
    测试代码如下：
    \begin{verbatim}
    vector<int>obj;
    for (i = 10; i >0; i--)
        {
            obj.push_back(i);
        }
    clock_t startTime_0 = clock();
    BSTSorting(obj, 0);                     ///_mode = 0时的测试
    clock_t endTime_0 = clock();

    cout<<"_mode = 0最坏效率用时:"<<double(endTime_0 - startTime_0)<<"ms"<<endl;
    
    \end{verbatim}
    测试结果：
    \begin{figure}[htbp]
      \centering
      \includegraphics[scale=0.3]{_mode=0.png}
      \caption{$\_mode = 0$时最坏效率测试结果}
    \end{figure} 




    2.2     \textbf{$\_mode = 1$时的平均效率} 
    
    
    测试代码如下：
    \begin{verbatim}
    vector<int>obj;
    for (i = 10; i >0; i--)
        {
            obj.push_back(i);
        }
    double avarage=0;               
    for(i=1;i<=10;i++)
        {
        clock_t startTime_1 = clock();
        BSTSorting(obj, 1);                     ///_mode = 1时的测试
        clock_t endTime_1 = clock();
        avarage=avarage+double(endTime_1 - startTime_1);
        }
    
    cout<<"_mode = 1平均效率用时:"<<avarage/10<<"ms"<<endl;
    
    \end{verbatim}
    测试结果：
    \begin{figure}[htbp]
      \centering
      \includegraphics[scale=0.3]{_mode=1.png}
      \caption{$\_mode = 1$时平均效率测试结果}
    \end{figure} 



\end{enumerate}

\section{脚本文件Bash run 的使用}
\begin{enumerate}
\item 创建一个Bash文件
首先是.sh使用以下命令创建带有扩展名的新文本文件
\begin{verbatim}
touch run.sh
\end{verbatim}
\item 编写脚本文件
\begin{verbatim}
g++ -o test src/TestBinarySearchTree.cpp

 -I/home/student/桌面/数据结构作业二/include
./test
\end{verbatim}
\item 执行脚本文件
\begin{verbatim}
bash run
\end{verbatim}
\end{enumerate}

\section{结论}
    二叉排序树查找算法的平均查找长度并不是一成不变的，
    主要取决于树的高度，即与二叉树的形态有关。 
    本文测试的最坏情况，即二叉树只有右(左)孩子，
    如果二叉排序树是一个只有右(左)孩子的单支树，
    其平均查找长度和单链表相同为O(n)； 
    而当其为平衡二叉树时，
    平衡二叉树的平均查找长度O(logN）。 
    补充:当有序表是静态查找表时，宜用顺序表作为其存储结构，而采用二分查找实现其查找操
    作当有序表是动态查找表时，应选择二叉排序树作为其逻辑结构

 













\end{document}
